An online auction is a widely used mechanism for selling advertisements using Internet search engines. Each time a user enters a search term into a search engine, the online auction allocates the advertising space within that user's search results. There are hundreds of millions of separate online auctions conducted every day. Search engines' revenues from online auctions are on the order of ten billion dollars per year. As a result, these advertising auctions are receiving considerable attention from practitioners and academics. For example, Abrams, Z., Revenue Maximization When Bidders Have Budgets, In Proceedings the ACM-SIAM Symposium on Discrete Algorithms, 2006, considers the role of bid increment; Feng, J., Bhargava, H., and Pennock, D., Implementing Sponsored Search in Web Search Engines: Computational Evaluation of Alternative Mechanisms, INFORMS Journal on Computing, 2005, consider the implications of ranking rules; and Borgs, C., et al., Multi-Unit Auctions with Budget-Constrained Bidders, In Proceedings the Sixth ACM Conference on Electronic Commerce, Vancouver, BC, 2005 consider the effect of budgets; and Szymanski, B. and Lee, J., Impact of ROI on Bidding and Revenue in Sponsored Search Advertisement Auctions, Second Workshop on Sponsored Search Auctions, 2006, use simulations to study sponsored search auctions.
However, these theoretical analyses of online auctions have neglected the role and importance of the reserve price for auctioneers in multi-unit auctions. Myerson, R., Optimal Auction Design, Mathematics of Operation Research 6, 58-73, 1981, proves that adding a reserve price to an otherwise efficient auction is an optimal mechanism in a single-unit auction in the case of symmetric bidders. In general, the auction for search advertisements is a multi-unit auction, and optimal mechanism design in multi-unit auctions are an open problem. See for example, Chawla, C., Hartline, J., Klienberg, B., Approximately Optimal Multi-Product Pricing, with and without Lotteries, Bay Algorithmic Game Theory Symposium, September 2006.
An online keyword auction represents a double-sided auction where there may be a buyer and a seller. There have been several attempts to design budget balanced mechanisms for double-sided auctions where both the buyers and sellers are strategic and the goods are either homogeneous or heterogeneous. When designing a mechanism for implementing a trading market such as a double-sided auction, there are several key properties that are desirable to maintain. Some of the more important ones are individual rationality (“IR”)—to make it worthwhile for all traders to participate, incentive compatibility (“IC”)—to give incentive to traders to report their true value to the mechanism, and budget balance (“BB”)—not to run the mechanism on a loss. See for example, McAfee R. P. A Dominant Strategy Double Auction, Journal of Economic Theory, Volume 56, pages 434-450, 1992, and Y. Bartal, R. Gonen and P. La Mura, Negotiation-range Mechanisms: Exploring the Limits of Truthful Efficient Markets, Electronic Commerce 2004: Proceedings of the 5th ACM Conference on Electronic Commerce, 2004. In McAfee, a mechanism is developed that, given valuations of buyers and sellers, produces an allocation (which are the trading players) and a matching between buyers and sellers such that the mechanism is IR, IC, and BB.
What is needed is a system and method for a double-sided auction that may optimize the reserve price and allocation of web page placements. Such a system and method should be able to maximize revenue while bounding any loss of efficiency of the online keyword auction.